package com.lw.leetcode.dp.b;

/**790. 多米诺和托米诺平铺
 * @Author liw
 * @Date 2021/9/25 13:07
 * @Version 1.0
 */
public class NumTilings {

    public static void main(String[] args){
        NumTilings test = new NumTilings();
        // 979232805
        int n =1000;
        int i = test.numTilings(n);

        System.out.println(i);
    }

    public int numTilings(int n) {
        if (n < 3) {
            return n;
        }
        long a1 = 1;
        long a2 = 1;
        long a3 = 1;
        long b1 = 2;
        long b2 = 2;
        long b3 = 2;
        long c1;
        long c2;
        long c3;
        for (int i = 2; i <n; i++) {
            c1 = (a1 + b1 + a2 + a3) % 1000000007;
            c2 = (b1 + b3) % 1000000007;
            c3 = (b1 + b2) % 1000000007;
            a1 =b1;
            a2 = b2;
            a3 = b3;
            b1 = c1;
            b2 = c2;
            b3 = c3;
        }
        return (int) b1;
    }

    public int numTilings2(int n) {
        if (n < 3) {
            return n;
        }
        long[][] arr = new long[n][3];
        arr[0][0] = 1;
        arr[0][1] = 1;
        arr[0][2] = 1;
        arr[1][0] = 2;
        arr[1][1] = 2;
        arr[1][2] = 2;
        for (int i = 2; i <n; i++) {
            arr[i][0] = (arr[i - 2][0] + arr[i - 1][0] + arr[i - 2][1] + arr[i - 2][2]) % 1000000007;
            arr[i][1] = (arr[i - 1][0] + arr[i - 1][2]) % 1000000007;
            arr[i][2] = (arr[i - 1][0] + arr[i - 1][1]) % 1000000007;
        }
        return (int) arr[n - 1][0];
    }
}
